package com.atguigu.search;

import java.util.ArrayList;
import java.util.List;

//二分法查找
//前提是数组有序

/*
 * 1.首先确定该数组的中间值的下标mind=(left+right)/2
 * 2.findVal和arr[mid]进行比较
 *  2.1>，在mid的右边进行递归
 *  2.2<，在mid的左边进行递归
 *  2.3=，说明找到了，返回
 * 什么时候结束递归
 * 找到就结束了递归
 * 递归完整个数组，没有找到就结束退出
 * */
public class BinarySerach {
    public static void main(String[] args) {

        int[] arr={1,2,3,7,8,4,5,9,9,10,10,10,10,10};
        int i = binarySearch(arr,0,arr.length-1,1);
        System.out.println(i);
        System.out.println("多个相同值");
        List<Integer> integers = listBinarySearch(arr, 0, arr.length - 1, 9);
        System.out.println(integers);

    }
    public static int binarySearch(int[] arr,int left,int right,int val){
        System.out.println("ll");
        if(left>right){
            throw new RuntimeException("没有这个数");

        }
        int mid=left+(right-left)/2;
        if(val<arr[mid]){
             return binarySearch(arr,left,mid-1,val);
        }else if(val>arr[mid]){
           return binarySearch(arr,mid+1,right,val);
        }else {
            return mid;
        }


    }
    //当有多个目标值
    public static List<Integer> listBinarySearch(int[] arr,int left,int right,int val){
        List<Integer> list = new ArrayList<>();
        if(left>right){
            return null;

        }
        int mid=left+(right-left)/2;
        if(val<arr[mid]){
            return listBinarySearch(arr,left,mid-1,val);
        }else if(val>arr[mid]){
            return listBinarySearch(arr,mid+1,right,val);
        }else {
            list.add(mid);
            int left_temp=mid-1;
            while (true){
                if(left_temp<0||arr[left_temp]!=val){
                    break;
                }
                list.add(left_temp);
                left_temp--;
            }
            int right_temp=mid+1;
            while (true){
                if(right_temp>arr.length-1||arr[right_temp]!=val){
                    break;
                }
                list.add(right_temp);
                right_temp++;
            }
            return list;

        }
    }
}
